package com.wrial.kind.sort;
/*
 * @Author  Wrial
 * @Date Created in 9:58 2020/8/26
 * @Description 数组中的逆序对
 * 在数组中的两个数字，如果前面一个数字大于后面的数字，则这两个数字组成一个逆序对。
 * 输入一个数组，求出这个数组中的逆序对的总数。
 * 输入: [7,5,6,4]
   输出: 5
 */

public class ReversePairs {

    /**
     * 1.暴力遍历法，会有很多的重复计算，因为暴力法是没有记忆性的
     * 2.归并排序法  因为归并排序是分段的，前一段的物理位置是一定小于后一段的物理位置
     * 因此只需在归并排序的时候，如果选择的是后一段数组上的值，那就说明有逆转，就将前一段剩下的那部分加入到sum
     */
    int sum = 0;

    public int reversePairs(int[] nums) {
        if (nums.length < 2) return 0;
        int[] temp = new int[nums.length];
        merge(nums, 0, nums.length - 1, temp);

        return sum;

    }

    /**
     * 先分再和
     *
     * @param nums
     * @param l
     * @param r
     * @param temp
     */
    private void merge(int[] nums, int l, int r, int[] temp) {
        if (l == r) return; //如果只有一个数，那就不存在逆序数
        int mid = l + (r - l) / 2;//可以防止大数情况下的越界
        merge(nums, l, mid, temp);
        merge(nums, mid + 1, r, temp);
        sort(nums, l, r, temp);
    }

    /**
     * 合并
     */
    private void sort(int[] nums, int l, int r, int[] temp) {
        int mid = l + (r - l) / 2;
        int pr = mid + 1, pl = l;
        int p = 0;
        while (pl <= mid && pr <= r) {
            if (nums[pr] < nums[pl]) {
                sum += mid - pl + 1;
                temp[p++] = nums[pr++];
            } else {
                temp[p++] = nums[pl++];
            }
        }
        while (pl <= mid) {
            temp[p++] = nums[pl++];
        }
        while (pr <= r) {
            temp[p++] = nums[pr++];
        }
        for (int i = l; i <= r; i++) {
            nums[i] = temp[i - l];
        }
    }

    public static void main(String[] args) {
        int[] arr = new int[]{1, 3, 2, 3, 1};
        ReversePairs reversePairs = new ReversePairs();
        reversePairs.reversePairs(arr);
        for (int i : arr) {
            System.out.println(i);
        }
    }
}
